package com.ljx.Dynamic;

/**
 * @author 李加喜
 * @Package com.ljx.Dynamic
 * @date 2021-11-02 20:08
 */

/**
 * 题目509  斐波那契数
 */
public class One {
    public static void main(String[] args) {
        System.out.println(fib(10));
    }
    public static int fib(int n){
        if (n<1) {
            return 0;
        }
        int[] sum=new int[n+1];
        return help(sum,n);
    }
    public static int help(int[] sum,int n){
        if (n==1 || n==2) {
            return 1;
        }
        if (sum[n]!=0) {
            return sum[n];
        }
        sum[n]=help(sum, n-1)+help(sum, n-2);
        return sum[n];
    }
}
